package 力扣;

/**
 * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 示例：
 root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

     10
     /  \
     5   -3
     / \    \
     3   2   11
     / \   \
     3  -2   1

 返回 3。和等于 8 的路径有:

 1.  5 -> 3
 2.  5 -> 2 -> 1
 3.  -3 -> 11
 */
public class _437路径总和_III {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public int pathSum(TreeNode root, int sum) {
        if( root == null ) return 0;

        int cnts = dfs(root,sum) + pathSum(root.left,sum) +pathSum(root.right,sum);
        return cnts;
    }

    private int dfs(TreeNode root, int sum) {
        if( root == null) return 0;
        int ret = 0;
        if( root.val == sum) ret ++;
        ret += dfs(root.left, sum-root.val) +dfs(root.right, sum-root.val);
        return ret;
    }
}
